{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Strange Printer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: strangePrinter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #奇怪的打印机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有台奇怪的打印机有以下两个特殊要求：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>打印机每次只能打印由 <strong>同一个字符</strong> 组成的序列。</li>\n",
    "\t<li>每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> ，你的任务是计算这个打印机打印它需要的最少打印次数。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaabbb\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>首先打印 \"aaa\" 然后打印 \"bbb\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aba\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>首先打印 \"aaa\" 然后在第二个位置打印 \"b\" 覆盖掉原来的字符 'a'。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [strange-printer](https://leetcode.cn/problems/strange-printer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [strange-printer](https://leetcode.cn/problems/strange-printer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaabbb\"', '\"aba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        merges = ''\n",
    "        for i in s:\n",
    "            if merges and i==merges[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                merges += i\n",
    "        n = len(merges)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if merges[i] == merges[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    minnum = float('inf')\n",
    "                    for k in range(i, j):\n",
    "                        minnum = min(minnum, dp[i][k] + dp[k+1][j])\n",
    "                    dp[i][j] = minnum\n",
    "        \n",
    "\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[n for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):dp[i][i]=1\n",
    "        for j in range(1,n):\n",
    "            for i in range(j-1,-1,-1):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        # print(dp)\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        s = ''.join([s[0]] + [s[i] if s[i] != s[i-1] else '' for i in range(1, len(s))])\n",
    "        n = len(s)\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for N in range(1, n + 1):\n",
    "            for l in range(n - N + 1):\n",
    "                r = l + N - 1\n",
    "                f[l][r] = f[l+1][r] + 1\n",
    "                for k in range(l+1, r+1):\n",
    "                    if s[k] == s[l]:\n",
    "                        f[l][r] = min(f[l][r], f[l][k-1]+f[k+1][r])\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        f=[[inf for i in range(n)]for i in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][i]=1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    f[i][j]=f[i][j-1]\n",
    "                    continue\n",
    "                for k in range(i,j):\n",
    "                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])\n",
    "        return f[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        #dp[i][j]表示打印区间s[i:j]的最少打印次数\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "        for length in range(2,n+1):\n",
    "            for i in range(n-length+1):\n",
    "                j=i+length-1\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i+1][j])\n",
    "                #状态转移\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        if s[i]==s[k]:\n",
    "                            #可以一起打印\n",
    "                            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        size=len(s)\n",
    "        dp=[[float(\"inf\")]*size for _ in range(size)]\n",
    "\n",
    "        for i in range(size-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,size):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j])\n",
    "        return dp[0][size-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for i in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "                else:\n",
    "                    mmin = 1919810\n",
    "                    for k in range(i, j):\n",
    "                        mmin = min(mmin, dp[i][k] + dp[k + 1][j])\n",
    "                    dp[i][j] = mmin\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        dp=[[0]*len(s) for _ in range(len(s))]\n",
    "        for i in range(len(s)):dp[i][i]=1\n",
    "        for n in range(2,len(s)+1):\n",
    "            for l,r in enumerate(x+n-1 for x in range(len(s)-n+1)):dp[l][r]=dp[l][r-1] if s[l]==s[r] else min(dp[l][i]+dp[i+1][r] for i in range(l,r))\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        f[i][j] = min(f[i][j], f[i][k] + f[k+1][j])\n",
    "        return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for __ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[j][i] = min(dp[j+1][i-1] + 1, dp[j][i-1],dp[j+1][i])\n",
    "                else:\n",
    "                    dp[j][i] = min([dp[j][k]+ dp[k+1][i] for k in range(j,i)])\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "    \n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "\n",
    "    \n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    mi=float(\"inf\")\n",
    "                    for k in range(i,j):\n",
    "                        mi=min(mi,dp[i][k]+dp[k+1][j])\n",
    "                    dp[i][j]=mi\n",
    "        #print(dp)\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "    # 暴力递归版本\n",
    "    def strangePrinter1(self, s):\n",
    "        if s == None or len(s) == 0:\n",
    "            return 0\n",
    "\n",
    "        sl = list(s)\n",
    "        return self.process1(sl, 0, len(sl) - 1)\n",
    "    \n",
    "    # 要想刷出str[L...R]的样子！\n",
    "\t# 返回最少的转数\n",
    "    def process1(self, sl, L, R):\n",
    "        # base case\n",
    "        # 如果区间只是1了，则当前区间最优肯定就是刷1次\n",
    "        if L == R:\n",
    "            return 1\n",
    "\n",
    "        # 当前区间，刷的次数的最大值，肯定不超过区间内元素的个数\n",
    "        # 这里用区间内元素个数，来当做最大值，来获取最小的结果\n",
    "        # 区间[L, R]，包含L，所以，要+1\n",
    "        ans = R - L + 1\n",
    "        \n",
    "        # 确定第一次刷，肯定是从L位置开始，这肯定包含最优解\n",
    "        #   在这个前提下，尝试，以k为分界点，两边不进行跨界刷\n",
    "        #   然后，将两边不跨界刷的次数，相加，就是总区间的次数\n",
    "        for k in range(L + 1, R + 1, 1):\n",
    "            # 区间分隔为[L, k - 1], [k, R]两个部分\n",
    "            ans = min(ans, self.process1(sl, L, k - 1) + \n",
    "                      self.process1(sl, k, R) - \n",
    "                      # 注意，这里是不跨界下的特殊情况\n",
    "                      # 由于当L和k位置元素相同的情况下，上面是，不跨界的情况\n",
    "                      #   但跨界的情况，肯定是最优的，所以，2次，合并为1次，肯定是最优的\n",
    "                      (1 if sl[L] == sl[k] else 0)\n",
    "                      )\n",
    "        # 所有可能性区间，投票选出最小的，来进行pk形成结果，肯定是最小的\n",
    "        #   这就是递归的核心：\n",
    "        #     所有可能性下的pk。\n",
    "        #     大的最小，肯定包含，每步的最小的可能情况\n",
    "        return ans\n",
    "    \n",
    "    # 傻缓存法\n",
    "    # 由，暴力递归版本，直接修改过来的\n",
    "    def strangePrinter2(self, s):\n",
    "        if s == None or len(s) == 0:\n",
    "            return 0\n",
    "\n",
    "        sl = list(s)\n",
    "        N = len(sl)\n",
    "        \n",
    "        # 缓存dp[L][R]的结果\n",
    "        dp = [[0 for j in range(N)] for i in range(N)]\n",
    "        return self.process2(sl, 0, N - 1, dp)\n",
    "    \n",
    "    def process2(self, sl, L, R, dp):\n",
    "        # 命中傻缓存\n",
    "        if dp[L][R] != 0:\n",
    "            return dp[L][R]\n",
    "        ans = R - L + 1\n",
    "        \n",
    "        if L == R:\n",
    "            ans = 1\n",
    "        else:\n",
    "            for k in range(L + 1, R + 1, 1):\n",
    "                ans = min(ans, self.process2(sl, L, k - 1, dp) + \n",
    "                        self.process2(sl, k, R, dp) - \n",
    "                        (1 if sl[L] == sl[k] else 0)\n",
    "                        )\n",
    "        # 缓存当前最优结果\n",
    "        dp[L][R] = ans\n",
    "        return ans\n",
    "    \n",
    "    # 动态规划版本\n",
    "    # 由暴力递归修改而来，本质也是缓存\n",
    "    def strangePrinter(self, s):\n",
    "        if s == None or len(s) == 0:\n",
    "            return 0\n",
    "\n",
    "        sl = list(s)\n",
    "        N = len(sl)\n",
    "\n",
    "        # dp[L][R]\n",
    "        dp = [[0 for j in range(N)] for i in range(N)]\n",
    "        # 基础填写\n",
    "        # L = R的时候，肯定只有1次\n",
    "        # 当只有L和L + 1的时候，如果两个相等，肯定只有1次，否则就是2次\n",
    "        dp[N - 1][N - 1] = 1\n",
    "        for i in range(N - 1):\n",
    "            dp[i][i] = 1\n",
    "            dp[i][i + 1] = 1 if sl[i] == sl[i + 1] else 2\n",
    "            \n",
    "        # 由于R不可能<L,所以，只有右上半部分可以填写\n",
    "        # L是从N - 3开始的，因为，N - 1, N - 2上面都计算了\n",
    "        # 从右下，往上填\n",
    "        for L in range(N - 3, -1, -1):\n",
    "            # L + 1,位置，已经计算了\n",
    "            for R in range(L + 2, N, 1):\n",
    "                dp[L][R] = R - L + 1\n",
    "                for k in range(L + 1, R + 1, 1):\n",
    "                    # 根据依赖，所以，决定是从右下开始\n",
    "                    #                        依赖左侧\n",
    "                    dp[L][R] = min(dp[L][R], dp[L][k - 1] + \n",
    "                            # 依赖下侧\n",
    "                            dp[k][R] - \n",
    "                            (1 if sl[L] == sl[k] else 0)\n",
    "                            )\n",
    "        return dp[0][N - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if j - i < 1:\n",
    "        #         return 1\n",
    "        #     res = float('inf')\n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i, j-1)\n",
    "        #     else:\n",
    "        #         for k in range(i, j):\n",
    "        #             res = min(res, dfs(i, k) + dfs(k+1, j))\n",
    "        #         return res\n",
    "        # return dfs(0, len(s)-1)\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]  \n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i][j-1]\n",
    "                else:\n",
    "                    res = float('inf')\n",
    "                    for k in range(i, j):\n",
    "                        res = min(res, f[i][k]+f[k+1][j])\n",
    "                    f[i][j] = res\n",
    "        return f[0][n-1]\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        strs = list(s)\n",
    "        n = len(strs)\n",
    "        dp = [[n for j in range(n)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for L in range(n-2, -1, -1):\n",
    "            for R in range(L+1, n):\n",
    "                min_count = R - L + 1\n",
    "                for i in range(L + 1, R + 1):\n",
    "                    # L..i-1 先打印，i..R 在打印\n",
    "                    min_count = min(min_count, dp[L][i - 1] + dp[i][R] - (1 if strs[L] == strs[i] else 0))\n",
    "                dp[L][R] = min_count\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[float(\"inf\")]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        if not s:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        dp = [ [0]*(n) for i in range(n+1) ]\n",
    "\n",
    "        for l in range(n):\n",
    "            for i in range(n-l):\n",
    "                j = i + l\n",
    "                dp[i][j] = dp[i+1][j] + 1\n",
    "                for k in range(i+1, j+1):\n",
    "                    if s[k] == s[i]:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j])\n",
    "        \n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k-1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i][j - 1]\n",
    "                else:\n",
    "                    minimum = float('inf')\n",
    "                    for k in range(i, j):\n",
    "                        minimum = min(f[i][k] + f[k + 1][j], minimum)\n",
    "                    f[i][j] = minimum\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n= len(s)\n",
    "        dp = [[0]* n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1 \n",
    "\n",
    "        for l in range(1, n):\n",
    "            for i in range(n-l):\n",
    "                j = i + l \n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i+1][j], dp[i][j-1])\n",
    "                else:\n",
    "                    ans = float('inf')\n",
    "                    for k in range(i, j):\n",
    "                        ans = min(ans, dp[i][k] + dp[k+1][j])\n",
    "                    dp[i][j] = ans \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[inf]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    res = inf\n",
    "                    for k in range(i,j):\n",
    "                        res = min(res,dp[i][k]+dp[k+1][j])\n",
    "                    dp[i][j] = res\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        strs = list(s)\n",
    "        n = len(strs)\n",
    "        dp = [[-1 for j in range(n)] for i in range(n)]\n",
    "        return self.process2(strs, 0, n-1, dp)\n",
    "\n",
    "    # 从L...R打印出strs中的字符最少需要几次\n",
    "    # 限定每次L先打印，L打印好了后面也不需要变更了\n",
    "    # 第一次先打印L..i-1，后面在打印i..R。看i的分割点在哪里最好\n",
    "    # 因为每次都是从最左边开始，如果两次打印的最左边一样，可以一起打印，就可以减去1次\n",
    "    def process2(self, strs, L, R, dp):\n",
    "        if dp[L][R] != -1:\n",
    "            return dp[L][R]\n",
    "        if L == R:\n",
    "            dp[L][R] = 1\n",
    "            return 1\n",
    "        min_count = R - L + 1\n",
    "        for i in range(L+1, R+1):\n",
    "            # L..i-1 先刷，i..R 在刷。\n",
    "            min_count = min(min_count, self.process2(strs, L, i-1, dp) + self.process2(strs, i, R, dp) - (1 if strs[L] == strs[i] else 0))\n",
    "        dp[L][R] = min_count\n",
    "        return min_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # 区间[i,j]需要的最少打印次数\n",
    "        dp = [[101]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n-1):\n",
    "            dp[i][i+1] = 1 if s[i]==s[i+1] else 2\n",
    "        for L in range(3,n+1):\n",
    "            for i in range(0,n-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = dp[l+1][r]\n",
    "                else:\n",
    "                    for k in range(l,r):\n",
    "                        dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        dp[-1][-1] = 1\n",
    "        for i in range(n - 1):\n",
    "            dp[i][i] = 1\n",
    "            dp[i][i + 1] = 1 if s[i] == s[i + 1] else 2\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            for j in range(i + 2, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "                else:\n",
    "                    ans = inf\n",
    "                    for k in range(i, j):\n",
    "                        ans = min(ans, dp[i][k] + dp[k + 1][j])\n",
    "                    dp[i][j] = ans\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n + 1)]\n",
    "        for l in range(n):\n",
    "            for i in range(n - l):\n",
    "                j = i + l\n",
    "                dp[i][j] = dp[i + 1][j] + 1\n",
    "                for k in range(i + 1, j + 1):\n",
    "                    if s[k] == s[i]:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for __ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i+1][j-1] + 1, dp[i][j-1],dp[i+1][j])\n",
    "                else:\n",
    "                    dp[i][j] = min([dp[i][k]+ dp[k+1][j] for k in range(i,j)])\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        length = len(s)\n",
    "        cache = [[0]*length for _ in range(length)]\n",
    "\n",
    "        for i in range(length):\n",
    "            cache[i][i]=1\n",
    "        \n",
    "        for i in range(2,length+1):\n",
    "            for start in range(0,length-i+1):\n",
    "                end = start+i-1\n",
    "\n",
    "                if s[start]==s[end] :\n",
    "                    cache[start][end] =cache[start][end-1]\n",
    "                else:\n",
    "                    m=length\n",
    "                    for k in range(start,end):\n",
    "                        l = cache[start][k]+cache[k+1][end]\n",
    "                        if l <m:\n",
    "                            m =l\n",
    "                    cache[start][end]=m\n",
    "        \n",
    "        return cache[0][length-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # 1.dp[i][j] 表示打印出字符串 s 的区间 [i, j] 需要的最少操作次数\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        # 2.初始化dp[i][i]=1, 最后要算的是dp[0][n-1]\n",
    "        # 3.动态转移：\n",
    "        #   1) dp[i][j] = dp[i][j-1] + 1   (s[i] == s[j])\n",
    "        #   2) dp[i][j] = dp[i][k] + dp[k + 1][j]  (s[i] != s[j])\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = float('inf')\n",
    "                    for k in range(i, j):\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])\n",
    "            # print(dp)\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        if not s: return 0\n",
    "        N = len(s)\n",
    "        dp = [[0]*(N) for i in range(N+1)]\n",
    "        for l in range(N):     # 区间长度\n",
    "            for i in range(N-l):  # 区间起点\n",
    "                j = i + l            # 区间终点\n",
    "                dp[i][j] = dp[i+1][j] + 1 # 初始化\n",
    "                for k in range(i+1, j+1):   # 枚举分割点\n",
    "                    if s[k] == s[i]:    # 首位一样可减少一次\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        # acbcbaa\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        # for i in range(n - 1,-1,-1):\n",
    "        #     f[i][i] = 1\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         if s[i] == s[j]:\n",
    "        #             f[i][j] = f[i][j - 1]\n",
    "        #         else:\n",
    "        #             for k in range(i,j):\n",
    "        #                 f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j])\n",
    "        # return f[0][n - 1]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(0,n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[float('inf')] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][k] + dp[k + 1][j] for k in range(i, j))\n",
    "        return dp[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        dp = [[float('inf')] * len(s) for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    k = i\n",
    "                    while k < j:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])\n",
    "                        k += 1\n",
    "        return dp[0][len(s)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 -L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[inf]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    res = inf\n",
    "                    for k in range(i,j):\n",
    "                        res = min(res,dp[i][k]+dp[k+1][j])\n",
    "                    dp[i][j] = res\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        length = len(s)\n",
    "        cache = [[0]*length for _ in range(length)]\n",
    "\n",
    "        for i in range(length):\n",
    "            cache[i][i]=1\n",
    "        \n",
    "        for i in range(2,length+1):\n",
    "            for start in range(0,length-i+1):\n",
    "                end = start+i-1\n",
    "\n",
    "                if s[start]==s[end] :\n",
    "                    cache[start][end] =cache[start][end-1]\n",
    "                else:\n",
    "                    m=length\n",
    "                    for k in range(start,end):\n",
    "                        l = cache[start][k]+cache[k+1][end]\n",
    "                        if l <m:\n",
    "                            m =l\n",
    "                    cache[start][end]=m\n",
    "        \n",
    "        return cache[0][length-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[-1]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n-1):\n",
    "            dp[i][i+1] = 1 if s[i]==s[i+1] else 2\n",
    "        for l in range(n-3,-1,-1):\n",
    "            for r in range(l+2,n):\n",
    "                if s[l]==s[r]:\n",
    "                    dp[l][r] = dp[l][r-1]\n",
    "                else:\n",
    "                    ans = float('inf')\n",
    "                    for m in range(l,r):\n",
    "                        ans = min(ans,dp[l][m]+dp[m+1][r])\n",
    "                    dp[l][r] = ans\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[1] * (n+1) for _ in range(n+1)]\n",
    "        \n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            # dp[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    tmp = float('inf')\n",
    "                    for k in range(i, j):\n",
    "                        tmp = min(tmp, dp[i][k] + dp[k+1][j])\n",
    "                    dp[i][j] = tmp\n",
    "        # print(dp)\n",
    "        # for l in range(n):\n",
    "        #     for i in range(n-l):\n",
    "        #         j = i + l\n",
    "        #         for k in range(i, j):\n",
    "        #             # dp[i][j] = min(dp[i][j], )\n",
    "        #             if s[i] == s[j]:\n",
    "        #                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])\n",
    "        #             else:\n",
    "        #                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for l in range(1,n+1):\n",
    "            for i in range(n-l+1):\n",
    "                j = i + l - 1\n",
    "                if i == j:\n",
    "                    dp[i][j] = 1\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-1] + 1\n",
    "                        for k in range(i,j):\n",
    "                            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])\n",
    "        \n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def strangePrinter(self, s: str) -> int:\r\n",
    "        n=len(s)\r\n",
    "        dp=[[float('inf')]*n for _ in range(n)]     #打印[i,j]的最少操作数\r\n",
    "        for i in range(n-1,-1,-1):\r\n",
    "            dp[i][i]=1\r\n",
    "            for j in range(i+1,n):\r\n",
    "                if s[i]==s[j]:\r\n",
    "                    dp[i][j]=dp[i][j-1]\r\n",
    "                else:\r\n",
    "                    dp[i][j]=min(dp[i][j], min(dp[i][k]+dp[k+1][j] for k in range(i,j)))\r\n",
    "        \r\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def strangePrinter(self, s: str) -> int:\r\n",
    "        L=len(s)\r\n",
    "        dp=[[L]*L for _ in range(L)]\r\n",
    "        for i in range(L-1,-1,-1):\r\n",
    "            dp[i][i]=1\r\n",
    "            for j in range(i+1,L):\r\n",
    "                if s[i]==s[j]:\r\n",
    "                    dp[i][j]=dp[i+1][j]\r\n",
    "                else:\r\n",
    "\r\n",
    "                    for k in range(i,j):\r\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\r\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            dp[i][i] = 1\n",
    "            dp[i][i+1] = 1 if s[i] == s[i+1] else 2\n",
    "        dp[n-1][n-1] = 1\n",
    "        for l in range(n-3, -1, -1):\n",
    "            for r in range(l+1, n):\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = dp[l][r-1]\n",
    "                else:\n",
    "                    ans = 1000000\n",
    "                    for k in range(l, r):\n",
    "                        ans = min(ans, dp[l][k] + dp[k+1][r])\n",
    "                    dp[l][r] = ans\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        start = 0\n",
    "        end = 0\n",
    "        c = s[0]\n",
    "\n",
    "        diff_starts = []\n",
    "        for idx in range(1, n):\n",
    "            if s[idx] == c:\n",
    "                end += 1\n",
    "            else:\n",
    "                diff_starts.append((start, end, c))\n",
    "                start = idx\n",
    "                end = idx\n",
    "                c = s[idx]\n",
    "        diff_starts.append((start, end, c))\n",
    "\n",
    "        m = len(diff_starts)\n",
    "        dp = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if diff_starts[j][2] == diff_starts[i][2]:\n",
    "                    dp[j][i] = 1 + dp[j+1][i-1]\n",
    "                else:\n",
    "                    best = math.inf\n",
    "                    for k in range(j, i):\n",
    "                        best = min(best, dp[j][k] + dp[k+1][i])\n",
    "                dp[j][i] = best\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        size=len(s)\n",
    "        dp=[[float(\"inf\")]*size for _ in range(size)]\n",
    "        for i in range(size-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,size):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j])\n",
    "        return dp[0][size-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i][i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]: f[i][j] = f[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        f[i][j] = min(f[i][j], f[i][k] + f[k+1][j])\n",
    "        return f[0][n-1]\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        size=len(s)\n",
    "        dp=[[float(\"inf\")]*size for _ in range(size)]\n",
    "        for i in range(size-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,size):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j])\n",
    "        return dp[0][size-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def strangePrinter(self, s: str) -> int:\r\n",
    "        L=len(s)\r\n",
    "        dp=[[100]*L for _ in range(L)]\r\n",
    "        # for i in range(L):\r\n",
    "        for i in range(L-1,-1,-1):\r\n",
    "            dp[i][i]=1\r\n",
    "            for j in range(i+1,L):\r\n",
    "                if s[i]==s[j]:\r\n",
    "                    dp[i][j]=min(dp[i][j],dp[i][j-1])\r\n",
    "                else:\r\n",
    "                    cnt=100\r\n",
    "                    for k in range(i,j):\r\n",
    "                        cnt=min(cnt,dp[i][k]+dp[k+1][j])\r\n",
    "                    dp[i][j]=cnt\r\n",
    "\r\n",
    "        return dp[0][-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        #dp[i][j]表示打印区间s[i:j]的最少打印次数\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "        for length in range(2,n+1):\n",
    "            for i in range(n-length+1):\n",
    "                j=i+length-1\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i+1][j])\n",
    "                #状态转移\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        #dp[i][j]表示打印区间s[i:j]的最少打印次数\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "        for length in range(2,n+1):\n",
    "            for i in range(n-length+1):\n",
    "                j=i+length-1\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i+1][j])\n",
    "                #状态转移\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        if s[i]==s[k]:\n",
    "                            #可以一起打印\n",
    "                            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def strangePrinter(self, s: str) -> int:\r\n",
    "        L=len(s)\r\n",
    "        dp=[[L]*L for _ in range(L)]\r\n",
    "        for i in range(L-1,-1,-1):\r\n",
    "            dp[i][i]=1\r\n",
    "            for j in range(i+1,L):\r\n",
    "                if s[i]==s[j]:\r\n",
    "                    dp[i][j]=min(dp[i+1][j],dp[i][j-1])\r\n",
    "                else:\r\n",
    "\r\n",
    "                    for k in range(i,j):\r\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\r\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for L in range(1,n + 1):\n",
    "            for l in range(n + 1 - L):\n",
    "                r = l + L - 1\n",
    "                f[l][r] = f[l + 1][r] + 1\n",
    "                for k in range(l + 1,r + 1):\n",
    "                    if s[l] == s[k]:\n",
    "                        f[l][r] = min(f[l][r],f[l][k - 1] + f[k + 1][r])\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[float(\"inf\")]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        size = len(s)\n",
    "        # 打印第i个字符到第j个字符需要的最少打印次数\n",
    "        dp = [[float('inf') for _ in range(size)] for _ in range(size)]\n",
    "        # 区间[i,j]内只有1种字符，则最少打印次数为1\n",
    "        for i in range(size):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        for l in range(2, size + 1):\n",
    "            for i in range(size):\n",
    "                j = i + l - 1\n",
    "                if j >= size:\n",
    "                    break\n",
    "                # 区间[i,j]首尾相同，则考虑剩余区间[i, j-1]的情况\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                # 枚举分割点k，将区间[i,k]分为区间[i, k]与区间[k+1, j] \n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])\n",
    "        return dp[0][size - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        size = len(s)\n",
    "        dp = [[float('inf') for _ in range(size)] for _ in range(size)]\n",
    "        for i in range(size):\n",
    "            dp[i][i] = 1\n",
    "            \n",
    "        for l in range(2, size + 1):\n",
    "            for i in range(size):\n",
    "                j = i + l - 1\n",
    "                if j >= size:\n",
    "                    break\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])\n",
    "\n",
    "        return dp[0][size - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[float(\"inf\") for _ in range(n)]for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        size=len(s)\n",
    "        dp=[[float(\"inf\")]*size for _ in range(size)]\n",
    "        for i in range(size-1,-1,-1):\n",
    "            dp[i][i]=1\n",
    "            for j in range(i+1,size):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    for k in range(i,j):\n",
    "                        dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j])\n",
    "        print(dp)\n",
    "        return dp[0][size-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        cnt = []\n",
    "        nums = []\n",
    "        c = 0\n",
    "        x = s[0]\n",
    "        for i in range(len(s)):\n",
    "            if x == s[i]:\n",
    "                c += 1\n",
    "            else:\n",
    "                nums.append(x)\n",
    "                cnt.append(c) \n",
    "                c = 1\n",
    "                x = s[i]\n",
    "        nums.append(x)\n",
    "        cnt.append(c)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = dfs(i+1,j)+1 #此次只打印i,\n",
    "            for k in range(i+1,j):\n",
    "                if nums[k] == nums[i]:#k后面还有和nums[i]相同的，找到最后一个与nums[i]相同的，才计算一次打印 \n",
    "                    res = min(res,dfs(i+1,k)+dfs(k, j))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, len(nums))\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n",
    "        # # a b a b a\n",
    "        # [1,2] + [2,n]->[3,4],[4,5] 。最终划分分单个区间\n",
    "        # [1,2] -> 1\n",
    "        # [3,4] - >1\n",
    "        # [4,5]  -->1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        #dp[i][j]: 打印区间[i,j]的最少操作数\n",
    "        dp=[[float('inf') for _ in range(length)] for _ in range(length)]\n",
    "        for i in range(length):\n",
    "            dp[i][i]=1\n",
    "        for k in range(1,length):\n",
    "            i=0\n",
    "            for j in range(k,length): \n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    min_val=float('inf')\n",
    "                    for p in range(i, j):\n",
    "                        if p+1<=j:\n",
    "                            min_val=min(min_val, dp[i][p]+dp[p+1][j])\n",
    "                    dp[i][j]=min_val\n",
    "                i+=1\n",
    "        return dp[0][length-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        cnt = []\n",
    "        nums = []\n",
    "        c = 0\n",
    "        x = s[0]\n",
    "        for i in range(len(s)):\n",
    "            if x == s[i]:\n",
    "                c += 1\n",
    "            else:\n",
    "                nums.append(x)\n",
    "                cnt.append(c) \n",
    "                c = 1\n",
    "                x = s[i]\n",
    "        nums.append(x)\n",
    "        cnt.append(c)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = dfs(i+1,j)+1 #此次只打印i,\n",
    "            for k in range(i+1,j):\n",
    "                if nums[k] == nums[i]:\n",
    "                    res = min(res,dfs(i+1,k)+dfs(k, j))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, len(nums))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        stack = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "            elif stack and stack[-1] == c:\n",
    "                pass\n",
    "            elif len(stack) > 1 and stack[-2] == c:\n",
    "                cnt += 1\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i > j: return 0\n",
    "            ans = dp(i + 1, j) + 1\n",
    "            for k in range(i + 1, j + 1):\n",
    "                if stack[k] == stack[i]:\n",
    "                    ans = min(ans, dp(i, k - 1) + dp(k + 1, j))\n",
    "            return ans\n",
    "\n",
    "        return dp(0, len(stack) - 1) + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def solve(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            mn = solve(l, r-1) + 1\n",
    "            for i in range(l+1, r):\n",
    "                if s[i-1] == s[r-1]:\n",
    "                    mn = min(mn, solve(l, i) + solve(i, r-1))\n",
    "            return mn\n",
    "        return solve(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        stack = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "            elif stack and stack[-1] == c:\n",
    "                pass\n",
    "            elif len(stack) > 1 and stack[-2] == c:\n",
    "                cnt += 1\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i > j: return 0\n",
    "            ans = dp(i + 1, j) + 1\n",
    "            for k in range(i + 1, j + 1):\n",
    "                if stack[k] == stack[i]:\n",
    "                    ans = min(ans, dp(i, k - 1) + dp(k + 1, j))\n",
    "            return ans\n",
    "\n",
    "        return dp(0, len(stack) - 1) + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def f(i, j):\n",
    "            if i > j: return 0\n",
    "            ans = f(i, j - 1) + 1\n",
    "            for k in range(j-1,i-1,-1):\n",
    "                if s[k]== s[j]:\n",
    "                    ans = min(ans, f(i, k - 1) + f(k + 1, j))\n",
    "            return ans\n",
    "        return f(0, len(s) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(start, end):\n",
    "            if start >= end:\n",
    "                return 0\n",
    "            mn = 1 + dfs(start + 1, end)\n",
    "            for i in range(start + 1, end):\n",
    "                if s[start] == s[i]:\n",
    "                    mn = min(mn, dfs(start, i) + dfs(i + 1, end))\n",
    "            return mn\n",
    "        return dfs(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        @functools.lru_cache(maxsize=None)\n",
    "        def dp(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            ret = dp(i+1, j) + 1\n",
    "            for k in range(i+1, j+1):\n",
    "                if s[i] != s[k]:\n",
    "                    continue\n",
    "                ret = min(ret, dp(i, k-1) + dp(k+1, j))\n",
    "            return ret\n",
    "\n",
    "        n = len(s)\n",
    "        return dp(0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        s = ''.join(k for k, _ in groupby(s)) # 去重\n",
    "        prev = [s.rfind(s[i], 0, i) for i in range(len(s))] # 前一个相同字符的下标\n",
    "\n",
    "        @cache\n",
    "        def dp(i: int, j: int) -> int:\n",
    "            if i >= j - 1:\n",
    "                return j - i\n",
    "            if s[i] == s[j - 1]:\n",
    "                return dp(i, j - 1)\n",
    "\n",
    "            min_ = 100\n",
    "            k = j - 1\n",
    "            while k > i: # 只在和最后字符相同的字符下标分割\n",
    "                min_ = min(dp(i, k) + dp(k, j), min_)\n",
    "                k = prev[k]\n",
    "            return min_\n",
    "\n",
    "        return dp(0, len(s))\n",
    "        return dp(0, len(stack) - 1) + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        stack = []\n",
    "        for i, c in enumerate(s):\n",
    "            if not stack or stack[-1] != c:\n",
    "                stack.append(c)\n",
    "\n",
    "        s = ''.join(stack)\n",
    "        last_seen = [-1] * 26\n",
    "        prev = [-1] * len(s)\n",
    "        for i, c in enumerate(s):\n",
    "            prev[i] = last_seen[ord(c) - ord('a')]\n",
    "            last_seen[ord(c) - ord('a')] = i\n",
    "\n",
    "        @cache\n",
    "        def dp(i: int, j: int) -> int:\n",
    "            if i >= j - 1:\n",
    "                return j - i\n",
    "            if s[i] == s[j - 1]:\n",
    "                return dp(i, j - 1)\n",
    "\n",
    "            min_ = 100\n",
    "            k = j - 1\n",
    "            while k > i: # 只在和最后字符相同的字符下标分割\n",
    "                min_ = min(dp(i, k) + dp(k, j), min_)\n",
    "                k = prev[k]\n",
    "            return min_\n",
    "\n",
    "        return dp(0, len(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        handledS, n = [s[0]], len(s)\n",
    "        for i in range(1, n): # aaabb与ab等价\n",
    "            if s[i] != s[i-1]:\n",
    "                handledS.append(s[i])\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j: # 只要一次打印\n",
    "                return 1\n",
    "            ans = float('inf')\n",
    "            # 如果i, j位置字符相等, 打印ab和打印aba次数是一样的\n",
    "            if handledS[i] == handledS[j]:\n",
    "                ans = min(ans, dfs(i, j-1))\n",
    "            for k in range(i, j):\n",
    "                ans = min(ans, dfs(i, k) + dfs(k+1, j))\n",
    "            return ans\n",
    "        ans =  dfs(0, len(handledS) - 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "\n",
    "            while i < j and s[i] == s[i+1]:\n",
    "                i += 1\n",
    "\n",
    "            while i < j and s[j] == s[j-1]:\n",
    "                j -= 1\n",
    "\n",
    "            if i == j:\n",
    "                return 1\n",
    "            \n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i, j-1)\n",
    "\n",
    "            return min(dfs(i, k) + dfs(k+1, j) for k in range(i, j))\n",
    "        \n",
    "        return dfs(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j - i < 1:\n",
    "                return 1\n",
    "            res = float('inf')\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i, j-1)\n",
    "            else:\n",
    "                for k in range(i, j):\n",
    "                    res = min(res, dfs(i, k) + dfs(k+1, j))\n",
    "                return res\n",
    "        return dfs(0, len(s)-1)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(start,end) -> int:\n",
    "            if start==end :\n",
    "                return 1\n",
    "            if s[start] == s[end]:\n",
    "                return dfs(start,end-1)\n",
    "            return min(dfs(start,i)+dfs(i+1,end) for i in range(start,end))\n",
    "        return dfs(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strangePrinter(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # l[i] 和 i相同的字符向左最左侧出现的位置\n",
    "        l = [i for i in range(n)]\n",
    "        r = [i for i in range(n)]\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                l[i+1] = l[i]\n",
    "        for i in range(n-1,0,-1):\n",
    "            if s[i] == s[i-1]:\n",
    "                r[i-1] = r[i]\n",
    "\n",
    "        # 状态 s[i:j] 打印需要的最短\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     # if i == j:\n",
    "        #     #     return 1\n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(r[i]+1, l[j]-1) + 1\n",
    "        #     res = inf\n",
    "        #     for k in range(i,j): #\n",
    "        #         # [i,k] [k+1,j] k=i...j-1\n",
    "        #         res = min(res, dfs(i,k) + dfs(k+1,j))\n",
    "        #     return res\n",
    "        # return dfs(0,n-1)\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     # if i == j:\n",
    "        #     #     return 1\n",
    "        #     # print(i,j, s[i:j+1])\n",
    "        #     if s[i] == s[j]:\n",
    "        #         res = dfs(r[i]+1, l[j]-1) + 1\n",
    "        #         if j - i > 3:\n",
    "        #             print(i,j, s[i:j+1])\n",
    "        #             print(\" =\", res)\n",
    "        #     else:\n",
    "        #         res = inf\n",
    "        #         for k in range(i,j): #\n",
    "        #             # [i,k] [k+1,j] k=i...j-1\n",
    "        #             res = min(res, dfs(i,k) + dfs(k+1,j))\n",
    "        #         if j - i > 3:\n",
    "        #             print(i,j, s[i:j+1])\n",
    "        #             print(\" /\", res)\n",
    "        #     return res\n",
    "        # return dfs(0,n-1)\n",
    "                \n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i, j-1)\n",
    "            res = inf\n",
    "            for k in range(i,j): #\n",
    "                # [i,k] [k+1,j] k=i...j-1\n",
    "                res = min(res, dfs(i,k) + dfs(k+1,j))\n",
    "            return res\n",
    "        return dfs(0,n-1)\n",
    "                \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
